# 64/100 二分查找-搜索二维矩阵
# leetcode第35题: https://leetcode.cn/problems/search-a-2d-matrix/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/6
from leetcode import test


def searchMatrix_bf(matrix: list[list[int]], target: int) -> bool:
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == target:
                return True

    return False


def searchMatrix_bis(matrix: list[list[int]], target: int) -> bool:
    m, n = len(matrix), len(matrix[0])
    for i in range(m):
        # 比较每行的最后一个数字以确定行号
        if (i == 0 and target <= matrix[0][n - 1]) or matrix[i - 1][n - 1] < target <= matrix[i][n - 1]:
            l, r = 0, n - 1
            while l <= r:
                # r − l是区间的长度（即 [l,r] 的宽度）, (r − l)>> 1 计算的是区间宽度的一半（即中点相对于 l 的偏移量）。
                mid = ((r - l) >> 1) + l
                if matrix[i][mid] == target:
                    return True
                elif matrix[i][mid] > target:
                    r = mid - 1
                else:
                    l = mid + 1
        return False
    return False


if __name__ == '__main__':
    inp = [{"matrix": [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], "target": 3},
           {"matrix": [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], "target": 13},
           {"matrix": [[1, 1]], "target": 0},
           {"matrix": [[1, 3]], "target": 3},
           {"matrix": [[1]], "target": 1},
           ]
    out = [True, False, False, True, True, ]
    test.test_function(searchMatrix_bf, inp, out)
    test.test_function(searchMatrix_bis, inp, out)
